package top.jafar.data.structures;

/**
 * 要求：有M个人为成一个圈，然后开始报数，当数到第N个人时，这个人出局，直到所有人出圈
 */
public class JosephQuestionDemo {
    public static void main(String[] args) {
        ChildList list = new ChildList();
        for (int i = 0; i < 10; i++) {
            list.add(new Child(i, "第"+(i+1)+"个孩子"));
        }
        list.startCount(4);
    }
}

class ChildList {
    private Child head;
    private int size;

    public void startCount(int n) {
        int count = 1;
        Child temp = head;
        while (size > 0) {
            if (count % n == 0) {
                remove(temp);
                System.out.println(temp.getName()+" out");
            }
            count++;
            temp = temp.getNext();
        }
    }

    public void add(Child child) {
        size++;
        if (head == null) {
            head = child;
            head.setNext(head);
        }else {
            Child temp = head;
            while (true) {
                if (temp.getNext() == head) {
                    child.setNext(head);
                    temp.setNext(child);
                    break;
                }
                temp = temp.getNext();
            }
        }
    }

    public void remove(Child child) {
        if (head == null) {
            System.err.println("队列为空");
            return ;
        }
        Child temp = head;
        while (true) {
            // 获取下级
            if (temp.getNext() == child) {
                temp.setNext(temp.getNext().getNext());
                size--;
                break;
            } else if (temp.getNext() == head) {
                // 遍历结束
                break;
            }
            temp = temp.getNext();
        }
    }

    public void showList() {
        Child temp = head;
        while (true) {
            System.out.println(temp);
            if (temp.getNext() == head) {
                break;
            }
            temp = temp.getNext();
        }
    }
}

class Child {
    private int id;
    private String name;
    private Child next;

    public Child(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Child getNext() {
        return next;
    }

    public void setNext(Child next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Child{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
